import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class LeetCode509 {
    public static void main(String[] args) {
        System.out.println(fib(3));
    }


    public static int fib(int n) {
        if (n == 0) {
            return 0;
        }

        int a = 0;
        int b = 1;
        while (n > 1) {
            b = a + b;
            a = b - a;
            n--;
        }
        return b;
    }

    public static int fib1(int n) {
        double sqrt5 = Math.sqrt(5);
        double fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);
        return (int) Math.round(fibN / sqrt5);
    }
}
